package com.kevin.Code.DP;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname HouseRobberii
 * @Description Leetcode 213. 打家劫舍 II 动态规划 中等难度 思路同Leetcode 198
 * @Date 2021/10/9 21:35
 * @Version 1.0
 */
public class HouseRobberii {

    /**
     * @param nums
     * @return
     */
    public int rob(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }


        //如果偷了第一间房子，则不能偷最后一间房子。
        int num1 = helper(nums, 0, len - 1);
        //如果偷最后一间房子，则不能偷第一间房子
        int num2 = helper(nums, 1, len);

        return Math.max(num1, num2);

    }


    /**
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private int helper(int[] nums, int start, int end) {

        int len = end - start;
        //1.明确动态数组的定义
        int dp[] = new int[len + 1];

        //2.初始化条件
//        dp[0] = 1;

        //3.动态转移方程 的转移条件
        dp[1] = nums[0 + start];
        for (int i = 2; i <= len; i++) {

            //如果选择当前一个物资进行偷窃，则其值为前2
            dp[i] = Math.max(dp[i - 2] + nums[start + i - 1], dp[i - 1]);


        }


        return dp[len];
    }


    public int rob1(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }


//        //如果偷了第一间房子，则不能偷最后一间房子。
//        int num1 = helper(nums, 0, len - 1);
//        //如果偷最后一间房子，则不能偷第一间房子
//        int num2 = helper(nums, 1, len);
        int[] nums1 = Arrays.copyOfRange(nums, 0, len - 1);
        int[] nums2 = Arrays.copyOfRange(nums, 1, len);


        int num1 = helper1(nums1);
        int num2 = helper1(nums2);

        return Math.max(num1, num2);

    }


    //从软件编程的角度出发 高内聚 低耦合
    private int helper1(int[] nums) {

        int len = nums.length;
        //1.明确动态数组的定义
        int dp[] = new int[len + 1];

        //2.初始化条件
//        dp[0] = 1;

        //3.动态转移方程 的转移条件
        dp[1] = nums[0];
        for (int i = 2; i <= len; i++) {

            //如果选择当前一个物资进行偷窃，则其值为前2
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);


        }


        return dp[len];
    }

    public static void main(String[] args) {
        HouseRobberii houseRobberii = new HouseRobberii();
        int[] nums = new int[]{1, 2, 3, 1};
        int i = houseRobberii.rob1(nums);
        System.out.println(i);
    }
}
